package may;

import java.util.Arrays;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-5-20 20:21
 * @description：
 * @modified By：
 * @version:
 */
public class May20 {
    /**
     * create by: 冯涛滔
     * description: 01背包问题效果: 在不超过背包容量的情况下 能最多能装到多少容量
     * 1. states 是背包容量状态的可能性数组 比如 states[6]=true就是 背包可以装满6格容量
     * 2. j = 如果要装下当前物品 最多可以在有多少格物品的情况下装
     * 定义状态: states数组 含义:背包可以被装到什么容量
     * 状态转移:在states[j] == true 证明这个物品可以在背包装了 j容量之后装背包
     * 初始化:0这个位置设置为true 将第一件物品装入背包减少循环次数
     * create time: 2020-5-20 21:12
     * @params [items, n, w] n物品个数 w就是背包容量
     * @return int
     */
    public static int knapsack2(int[] items, int n, int w) {
        boolean[] states = new boolean[w + 1]; // 默认值false
        states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
        states[items[0]] = true; //将第一件物品装进背包
        for (int i = 1; i < n; ++i) { // 动态规划
            //第二个循环是为了判断这个物品放进背包的话会有多少种情况
            //j是从大到小 从小到大会出问题 问题在哪?
            //从小到大的话就可能一个物品被无限放入比如 j = 1 1=true 2 = true ...背包满了
            for (int j = w - items[i]; j >= 0; --j) {//把第i个物品放入背包  只要这个物品大小没有超标至少都会尝试将物品当作第一件放进背包
                //j的意思这个物品不需要的空间大小 比如这个物品是5 背包大小是8 那么他至少可以在 0123 等四种情况下放进背包
                //所以j能遍历到states的情况都是能够放进去的情况
                 if (states[j]==true){ //有一种情况可以到达这个存储量 所以就将当前物品放进去
                     states[j+items[i]] = true; //在j容量的情况下将这个物品装入背包
                 }
            }
        }
        for (int i = w; i >= 0; --i) { // 输出结果
            if (states[i] == true){
                return i;
            }
        }
        return 0;
    }
    /**
     * create by: 冯涛滔
     * description: 背包问题升级版 加入价值 在有限的容量装入最有价值的东西
     * 定义状态: 在某个容量的情况下背包里的最大价值
     * 状态转移: 在这个物品放入背包之后当前价值超越了当前容量的状态的最大价值 res[j+weight[i]] = Math.max(res[j]+value[i],res[j+weight[i]]);
     * 初始化:res[0] = 0 第一个物品放进去
     * create time: 2020-5-20 21:26
     * @params [weight, value, n, w]
     * @return int
     */
    public static int knapsack3(int[] weight, int[] value, int n, int w) {
        int[] res = new int[w+1];//记录在各个容量的情况下最大的价值总数
        Arrays.fill(res, -1);//初始化所有值为-1
        res[0] = 0;
        res[weight[0]] = value[0];
        for (int i = 1; i < n ; i++) {
            for(int j = w-weight[i];j>=0;j--){
                if(res[j]!=-1){
                    res[j+weight[i]] = Math.max(res[j]+value[i],res[j+weight[i]]); //判断当前组合是不是最大价值
                }
            }
        }
        int max = 0;
        for (int i = 0; i < res.length; i++) {
            max = Math.max(max,res[i]);
        }
        return max;
    }
}


